package com.leetcode.partition2;

import com.leetcode.common.TreeNode;

import java.util.Objects;

/**
 * @author `RKC`
 * @date 2021/8/19 9:19
 */
public class LC106从中序与后序遍历序列构造二叉树 {

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) return null;
        return divide(inorder, postorder, 0, inorder.length, 0, postorder.length);
    }

    public static void main(String[] args) {
//        int[] inorder = { 9, 3, 15, 20, 7 };
        int[] inorder = { 4, 5, 2, 1, 6, 7, 3 };
//        int[] postorder = { 9, 15, 7, 20, 3 };
        int[] postorder = { 5, 4, 2, 7, 6, 3, 1 };
        System.out.println(Objects.requireNonNull(buildTree(inorder, postorder)).val);
    }

    /**
     * 中序区间：[inorderStart, inorderEnd)
     * 后序区间：[postorderStart, postorderEnd)
     */
    @SuppressWarnings("UnnecessaryLocalVariable")
    private static TreeNode divide(final int[] inorder, final int[] postorder, int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {
        if (postorderStart == postorderEnd) return null;
        //取出后序序列在有效区间的最后一个值
        int postorderLastValue = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(postorderLastValue);
        if (postorderEnd - postorderStart == 1) return root;
        //切割线位置，根据postorderLastValue将中序序列在有效区间划分为左右两个区间：[inorderStart, delimiterIndex)，[delimiterIndex, inorderEnd)
        int delimiterIndex = 0;
        for (delimiterIndex = inorderStart; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == postorderLastValue) break;
        }
        //根据查找的切割线位置切割中序数组，将中序序列分为左右两个子区间
        int leftInorderStart = inorderStart, leftInorderEnd = delimiterIndex;       //左中序序列：[leftInorderStart, leftInorderEnd)
        int rightInorderStart = delimiterIndex + 1, rightInorderEnd = inorderEnd;   //右中序序列：[rightInorderStart, rightInorderEnd)
        //切割后续序列
        int leftPostorderStart = postorderStart, leftPostorderEnd = postorderStart + delimiterIndex - inorderStart; //[leftPostorderStart, leftPostorderEnd)
        int rightPostorderStart = postorderStart + (delimiterIndex - inorderStart), rightPostorderEnd = postorderEnd - 1;//需要排除最后一个元素，最后一个元素已经构造了root节点
        System.out.printf("左中：[%d, %d), 右中：[%d, %d)\t左后：[%d, %d)，右后：[%d, %d)\n", leftInorderStart, leftInorderEnd, rightInorderStart, rightInorderEnd, leftPostorderStart,
                leftPostorderEnd, rightPostorderStart, rightPostorderEnd);
        root.left = divide(inorder, postorder, leftInorderStart, leftInorderEnd, leftPostorderStart, leftPostorderEnd);
        root.right = divide(inorder, postorder, rightInorderStart, rightInorderEnd, rightPostorderStart, rightPostorderEnd);
        return root;
    }
}
